/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
// 中心扩散法
const isDrome = function (s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--
    right++
  }
  return [left + 1, right]
}
var longestPalindrome = function(s) {
  let start = 0
  let end = 0
  for (let i = 0; i < s.length; i++) {
    // 奇数回文串
    let [left1, right1] = isDrome(s, i, i)
    // 偶数回文串
    let [left2, right2] = isDrome(s, i, i + 1)
    if (right1 - left1 > end - start) {
      start = left1
      end = right1
    }
    if (right2 - left2 > end - start) {
      start = left2
      end = right2
    }
  }
  return s.slice(start, end)
}
// @lc code=end
// 滑动窗口加对撞
// var ispend = function (s, start, end) {
//   while (start <= end) {
//     if (s[start++] !== s[end--]) return false
//   }
//   return true
// }
// var longestPalindrome = function(s) {
//   let start = 0
//   let end = s.length - 1
//   while (start < end) {
//     let tempEnd = end
//     while(tempEnd <= s.length - 1) {
//       let pStart = start
//       let pEnd = tempEnd
//       if (ispend(s, pStart, pEnd)) {
//         return s.slice(start, tempEnd + 1)
//       } else {
//         start++
//         tempEnd++
//       }
//     }
//     start = 0
//     end --
//   }
//   return s[0]
// };

// 动态规划
// 当子串大于2时，为回文串的条件为：
// 子串的头尾节点相同，并且dp[i+1][j-1]因为回文子串
// 当子串只有2个并且相同，也为回文串
// 那么dp的转移方程为dp[i][j] = dp[i+1][j-1]
// var longestPalindrome = function(s) {
//   let n = s.length
//   if (n < 2) {
//     return s;
//   }
//   let dp = Array.from({length: n}, () => [])
//   // 每一个字符都是回文子串
//   for (let i = 0; i < s.length; i++) {
//     dp[i][i] = true
//   }
//   let maxLen = 1
//   let begin = 0
  
//   for (let L = 2; L <= n; L++) {
//     for (let i = 0; i < n; i++) {
//       // 后面一个字符串
//       let j = i + L - 1
//       // j不能大于等于字符串长度
//       if (j >= n) break
      
//       if(s[i] !== s[j]) {
//         dp[i][j] = false
//       } else {
//         if (L === 2) {
//           dp[i][j] = true
//         } else {
//           dp[i][j] = dp[i + 1][j - 1]
//         }
//       }
//       if (dp[i][j] && L > maxLen) {
//         begin = i
//         maxLen = L
//       }
//     }
//   }
//   return s.slice(begin, begin + maxLen)
// }